/*
 * @Author: dadadaXU 1413107032@qq.com
 * @Date: 2025-02-08 16:58:41
 * @LastEditors: dadadaXU 1413107032@qq.com
 * @LastEditTime: 2025-02-08 22:47:36
 * @FilePath: \LeetCode\23.合并-k-个升序链表.cpp
 * @Description: 这是默认设置,请设置`customMade`, 打开koroFileHeader查看配置 进行设置: https://github.com/OBKoro1/koro1FileHeader/wiki/%E9%85%8D%E7%BD%AE
 */
/*
 * @lc app=leetcode.cn id=23 lang=cpp
 *
 * [23] 合并 K 个升序链表
 *
 * 方法1：使用失败者树进行多路归并
 * - 直接使用优先队列就可以解决
 *
 * 方法2：归并思想
 * - 利用归并排序的划分思想分解 vector
 *
 * 方法3（官方题解）：使用优先队列直接计算
 */

#include <vector>
#include <iostream>
#include <queue>

struct ListNode
{
    int val;
    ListNode *next;
    ListNode() : val(0), next(nullptr) {}
    ListNode(int x) : val(x), next(nullptr) {}
    ListNode(int x, ListNode *next) : val(x), next(next) {}
};

// @lc code=start
class Solution
{
public:
    std::vector<int> loserTree; // 非叶子结点 成功者[0]
    int kPath;                  // 归并路数

    void adjustLT(const std::vector<ListNode *> &lists, int winner)
    {
        int node = (winner + kPath) / 2; // 失败者树索引
        while (node > 0)
        {
            /* 被击败 */
            if (lists[winner] == nullptr ||
                (lists[loserTree[node]] != nullptr &&
                lists[winner]->val > lists[loserTree[node]]->val))
                std::swap(winner, loserTree[node]);
            node /= 2;
        }
        loserTree[0] = winner;
    }

    ListNode *mergeKLists_01(std::vector<ListNode *> &lists)
    {
        kPath = lists.size();
        if (kPath == 0)
            return nullptr;
        else if (kPath == 1)
            return lists[0];
        /* 初始化失败者树 lists[kPath] 默认最小值 */
        lists.emplace_back(new ListNode(std::numeric_limits<int>::min()));
        loserTree.resize(kPath, kPath);
        for (int i = kPath - 1; i >= 0; i--)
            adjustLT(lists, i);
        /* 利用失败者归并排序 */
        ListNode *result = new ListNode(); // 创建一个哑节点
        ListNode *rear = result;
        while (lists[loserTree[0]] != nullptr)
        {
            rear->next = lists[loserTree[0]];
            rear = rear->next;
            lists[loserTree[0]] = lists[loserTree[0]]->next;
            adjustLT(lists, loserTree[0]);
        }
        rear->next = nullptr;

        /* 删除哑结点 */
        rear = result;
        result = result->next;
        delete rear;

        return result;
    }

    ListNode *mergeTwoLists(ListNode *list1, ListNode *list2)
    {
        ListNode *p1 = list1;
        ListNode *p2 = list2;
        ListNode *list3 = nullptr;
        ListNode *rear = nullptr;
        ListNode *temp = nullptr;

        if (p1 != nullptr && p2 != nullptr)
        {
            if (p1->val < p2->val)
            {
                list3 = p1;
                p1 = p1->next;
            }
            else
            {
                list3 = p2;
                p2 = p2->next;
            }
        }
        else if (p1 != nullptr)
            return list1;
        else if (p2 != nullptr)
            return list2;
        else
            return nullptr;

        rear = list3;
        while (p1 != nullptr && p2 != nullptr)
        {
            if (p1->val < p2->val)
            {
                temp = p1;
                p1 = p1->next;
            }
            else
            {
                temp = p2;
                p2 = p2->next;
            }

            rear->next = temp;
            rear = rear->next;
        }

        if (p1 != nullptr)
            rear->next = p1;
        if (p2 != nullptr)
            rear->next = p2;

        return list3;
    }

    ListNode *mergeSubLists(std::vector<ListNode *> &lists, int low, int high)
    {
        if (low == high)
            return lists[low];

        int mid = (low + high) / 2;
        return mergeTwoLists(
            mergeSubLists(lists, low, mid),
            mergeSubLists(lists, mid + 1, high));
    }

    ListNode *mergeKLists_02(std::vector<ListNode *> &lists)
    {
        int len = lists.size();
        if (len == 0)
            return nullptr;
        else
            return mergeSubLists(lists, 0, len - 1);
    }

    class Compare
    {
    public:
        bool operator()(ListNode *a, ListNode *b)
        {
            return a->val > b->val;
        }
    };

    std::priority_queue<ListNode *, std::vector<ListNode *>, Compare> minHeap;

    ListNode *mergeKLists_03(std::vector<ListNode *> &lists)
    {
        for (auto l : lists)
        {
            if (l != nullptr)
                minHeap.push(l);
        }

        ListNode *head = new ListNode();
        ListNode *rear = head;
        while (!minHeap.empty())
        {
            ListNode *node = minHeap.top();
            minHeap.pop();

            rear->next = node;
            rear = rear->next;

            if (node->next != nullptr)
                minHeap.push(node->next);
        }

        /* 删除哑结点 */
        rear = head;
        head = head->next;
        delete rear;

        return head;
    }
};
// @lc code=end

std::vector<ListNode *> createLinkedLists(const std::vector<std::vector<int>> &lists)
{
    std::vector<ListNode *> result;
    for (const auto &sublist : lists)
    {
        ListNode *dummy = new ListNode(0); // 创建一个哑节点
        ListNode *current = dummy;
        for (int val : sublist)
        {
            current->next = new ListNode(val);
            current = current->next;
        }
        result.push_back(dummy->next); // 去掉哑节点，加入链表头
        delete dummy;                  // 删除哑节点
    }
    return result;
}

int main(void)
{
    Solution solution;
    std::vector<ListNode *> lists = createLinkedLists({{1, 2, 2}, {1, 1, 2}, {}, {6, 10}});

    ListNode *result = solution.mergeKLists_01(lists);
    while (result != nullptr)
    {
        std::cout << result->val << " ";
        result = result->next;
    }
    std::cout << std::endl;

    return 0;
}